package api.list;

import java.util.NoSuchElementException;

/**
 * @author Ann Raboschuk
 *
 */
public class LinkedList<T> implements List<T>
{
   private static final long serialVersionUID = 1L;
   private Node<T> head, tail;
   private int size;
   
   public LinkedList()
   {
      head = tail = null;
      size = 0;
   }
   
   public Node<T> getHead()
   {
      return head;
   }
   
   @Override
   public void add(int index, T element)
   {
      if (index < 0 || index > size)
         throw new IndexOutOfBoundsException();
      if (index == size)
         this.addLast(element);
      else 
         if (index == 0)
            this.addFirst(element);
         else
         {
            Node<T> node = new Node<T>(element);
            Node<T> current = head;
            for (int i = 0; i < index; i++)
               current = current.getNext();
            node.setPrevious(current.getPrevious());
            current.getPrevious().setNext(node);
            current.setPrevious(node);
            node.setNext(current);
            size++;
         }
   }

   @Override
   public void addFirst(T element)
   {
      Node<T> node = new Node<T>(element);
      if (size != 0)
      {
         node.setNext(head);
         head.setPrevious(node);
      }
      else 
         tail = node;
      head = node;
      size++;
   }

   @Override
   public void addLast(T element)
   {
      Node<T> node = new Node<T>(element);
      if (size != 0)
      {
         tail.setNext(node);
         node.setPrevious(tail);
      }
      else
         head = node;
      tail = node;
      size++;
   }

   @Override
   public void clear()
   {
      head = tail = null;
      size = 0;
   }

   @Override
   public List<T> cloneList()
   {
      LinkedList<T> list = new LinkedList<T>();
      Node<T> current = head;
      while (current != null)
      {
         list.addLast(current.getData());
         current = current.getNext();
      }
      return list;
   }

   @Override
   public int contains(T element)
   {
      int index = -1;
      Node<T> current = head;
      for (int i=0; current != null; i++)
      {
         if (current.getData().equals(element))
         {
            index = i;
            break;
         }
         current=current.getNext();
      }
      return index;
   }

   @Override
   public void delete(int index)
   {
      if (index<0 || index >= size)
         throw new IndexOutOfBoundsException();
      if (index == 0)
         this.deleteFirst();
      else
      {
         if (index == size - 1)
            this.deleteLast();
         else
         {
            Node<T> current = head;
            for (int i = 0; i < index; i++)
               current = current.getNext();
            current.getPrevious().setNext(current.getNext());
            current.getNext().setPrevious(current.getPrevious());
            size--;
         }
      }
   }

   @Override
   public void deleteFirst()
   {
      if (size != 0)
      {
         if (size == 1)
            head = null;
         else
         {
            head = head.getNext();
            head.setPrevious(null);  
         }
         size--;
      }
   }

   @Override
   public void deleteLast()
   {
      if (size != 0)
      {
         if (size == 1)
            tail = null;
         else
         {
            tail = tail.getPrevious();
            tail.setNext(null);
         }
         size--;
      }
   }
   
   @SuppressWarnings("unchecked")
   @Override
   public boolean equals(Object list)
   {
      boolean equal = false;
      if (list != null && list instanceof LinkedList)
      {
         if (size == ((LinkedList<T>)list).size())
         {
            equal = true;
            Node<T> node2 = ((LinkedList<T>) list).getHead();
            Node<T> node1 = head;
            while (node2 != null)
            {
               if (!node2.getData().equals(node1.getData()))
               {
                  equal = false;
                  break;
               }
               node2 = node2.getNext();
               node1 = node1.getNext();
            }
         }
      }
      return equal;
   }

   @Override
   public T get(int index)
   {
      if (index < 0 || index > size - 1)
         throw new IndexOutOfBoundsException();
      Node<T> current = head;
      for (int i=1; i < index + 1; i++)
         current = current.getNext();
      return current.getData();
   }

   @Override
   public boolean isEmpty()
   {
      return size == 0;
   }

   @Override
   public Iterator<T> iterator()
   {
      return new Iterator<T>()
      {
         private Node<T> current = head;
         private int index = -1;
         
         public T next()
         {            
            T result = null;
            if (index == -1)
            {
               current = head;
               index++;
            }
            else
               current = current.getNext();
            if (current != null)
               result = current.getData();
            else
               throw new NoSuchElementException();
            return result;
         }
         
         public boolean hasNext()
         {
            boolean result = false;
            if (index==-1 && head != null)
               result = true;
            else
               if (current != null)
                  result = (current.getNext() != null);
            return result;
         }         
      };
   }

   @Override
   public void set(int index, T element)
   {
      if (index < 0 || index > size - 1)
         throw new IndexOutOfBoundsException();
      Node<T> current = head;
      for (int i = 1; i < index+1; i++)
         current = current.getNext();
      current.setData(element);
   }

   @Override
   public int size()
   {
      return size;
   }

   @SuppressWarnings("unchecked")
   @Override
   public void sort()
   {
      boolean changed = true;
      while (changed)
      {
         changed = false;
         Node<T> current = head;
         while (current.getNext() != null)
         {
            if (((Comparable<T>) current.getData()).compareTo(current.getNext().getData()) > 0)
            {
               T data = current.getData();
               current.setData(current.getNext().getData());
               current.getNext().setData(data);
               changed = true;
            }
            current = current.getNext();
         }
      }
   }

   @Override
   public List<T> sublist(int fromIndex, int toIndex)
   {
      if (fromIndex < 0 || toIndex > size)
         throw new IndexOutOfBoundsException();
      if (fromIndex >= toIndex)
         throw new IllegalArgumentException();
      LinkedList<T> list = new LinkedList<T>();
      Node<T> current = head;
      for (int i = 0; i < fromIndex; i++)
         current = current.getNext();
      for (int i = fromIndex; i < toIndex; i++)
      {
         list.addLast(current.getData());
         current = current.getNext();
      }
      return list;
   }
   
   //---------------------------------
   //for testing
   @SuppressWarnings("unchecked")
   public T[] getStorage()
   {
      T[] storage = (T[])new Object[size];
      Node<T> node = head;
      int i = 0;
      while (node != null)
      {
         storage[i++] = node.getData();
         node = node.getNext();
      }
      return storage;
   }
}
